package main.Q301_400;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Q391_400 {
    public static void main(String[] args) {
        System.out.println("Question391：");
        System.out.println("Question392：判断子序列");
        System.out.println("Question393：");
        System.out.println("Question394：字符串解码");
        System.out.println("Question395：至少有K个重复字符的最长子串");
        System.out.println("Question396：");
        System.out.println("Question397：");
        System.out.println("Question398：随机数索引");
        System.out.println("Question399：");
        System.out.println("Question400：");
    }
}

class Question392{
    public boolean isSubsequence(String s, String t) {//双指针
        if (s.length() == 0) return true;
        for (int i = 0, j = 0; j < t.length(); j++) {
            if (s.charAt(i) == t.charAt(j)) {
                if (++i == s.length())
                    return true;
            }
        }
        return false;
    }
}

class Question394{
    public String[] process(char[] s,int start){//遇到'['进入下一层递归，遇到']'返回本层递归结果，并返回本层递归后的坐标
        StringBuffer num=new StringBuffer(),str=new StringBuffer();
        String[] ans=new String[2];//0存结束位置，1存结果字符串
        int i=start;
        for (;i<s.length;){
            if (s[i]>='0'&&s[i]<='9') num.append(s[i]);
            else if (s[i]=='['){//进入下一层递归
                String[] temp=process(s,i+1);
                int times=Integer.valueOf(num.toString());
                num.delete(0,num.length());//重新计数
                for (int time=0;time<times;time++) str.append(temp[1]);
                i=Integer.valueOf(temp[0]);//下层递归结束位置
            }else if (s[i]==']'){//结束当前层递归
                ans[0]=String.valueOf(i);
                ans[1]=str.toString();
                break;
            }else {
                str.append(s[i]);
            }
            i++;
        }
        ans[0]=String.valueOf(i);
        ans[1]=str.toString();
        return ans;
    }
    public String decodeString(String s) {
        char[] str=s.toCharArray();
        String[] result=process(str,0);
        return result[1];
    }
}

class Question395{
    public boolean process(int[] chars,int k){
        for (int num:chars){
            if (num!=0&&num<k) return false;
        }
        return true;
    }
    public int longestSubstring(String s, int k) {
        int maxLength=0,length=s.length();
        boolean[] dp=new boolean[length];
        char[] str=s.toCharArray();
        for (int i=0;i<length;i++){
            int[] chars=new int[26];
            for (int j=i;j<length;j++){
                chars[str[j]-97]++;
                dp[j]=process(chars,k);
                if (dp[j]) maxLength=Math.max(maxLength,j-i+1);
            }
        }
        return maxLength;
    }
}

class Question398{
    private int[] Nums;
    public Question398(int[] nums) {
        this.Nums=nums;
    }

    public int pick(int target) {
        List<Integer> indexList=new ArrayList<>();
        for (int i=0;i<Nums.length;i++){
            if (Nums[i]==target) indexList.add(i);
        }
        int random=new Random().nextInt(indexList.size());
        return indexList.get(random);
    }
}